//
// Created by ct on 2021/11/5.
//

#ifndef ALGOANDSTRUCT_DAY5_H
#define ALGOANDSTRUCT_DAY5_H

#include <vector>
#include <queue>

using std::vector;
using std::queue;


// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Day5 {
public:
    static vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int>> ans;
        queue<TreeNode *> que;
        if (root)que.push(root);
        while (!que.empty()) {
            vector<int> vec;
            int size = (int) que.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *node = que.front();
                vec.push_back(node->val);
                que.pop();
                if (node->left)que.push(node->left);
                if (node->right)que.push(node->right);
            }

            ans.push_back(vec);
        }
        return ans;
    }

    // 翻转二叉树递归
    static TreeNode *invertTree(TreeNode *root) {
        if (!root)return nullptr;
        TreeNode *node = root->left;
        root->left = root->right;
        root->right = node;
        invertTree(root->right);
        invertTree(root->left);
        return root;
    }

    // 翻转二叉树非递归
    static TreeNode *invertTreeB(TreeNode *root) {
        if (!root)return nullptr;
        queue<TreeNode *> qu;
        TreeNode *ans = root;
        qu.push(root);
        while (!qu.empty()) {
            root = qu.front();
            qu.pop();
//            TreeNode * node = root->left;
//            root->left = root->right;
//            root->right = node;
            swap(root->left, root->right);
            if (root->left)qu.push(root->left);
            if (root->right)qu.push(root->right);
        }
        return ans;
    }

    // 二叉树的最大深度
    static int maxDepth(TreeNode *root) {
        if (!root)return 0;
        int max;

        max = 1 + maxDepth(root->left);

        int maxr;
        maxr = 1 + maxDepth(root->right);

//        if(max > maxr) {
//            return max;
//        }

        return max > maxr ? max : maxr;
    }

    // 二叉树的最大深度非递归
    static int maxDepthB(TreeNode *root) {
        if (!root)return 0;
        int max = 0;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            max++;
            int size = (int) que.size();
            for (int i = 0; i < size; ++i) {
                root = que.front();
                que.pop();
                if (root->left)que.push(root->left);
                if (root->right)que.push(root->right);
            }
        }
        return max;

    }

    /*
     给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。



     C++中序递归： 执行用时 : 12 ms, 在Validate Binary Search Tree的C++提交中击败了99.66% 的用户

class Solution {
public:
    int* last = NULL;
    bool isValidBST(TreeNode* root) {
        if (root){
            if(!isValidBST(root->left)) return false;
            if (last && *last>=root->val) return false;
            last = &root->val;
            if(!isValidBST(root->right)) return false;
            return true;
        }else return true;
    };
}
     */
    int *last = nullptr;

    bool isValidBST(TreeNode *root) {
        if(root){
            if(!isValidBST(root->left)) return false;
            if (last && *last>=root->val) return false;
            last = &root->val;
            if(!isValidBST(root->right)) return false;
            return true;
        } else return false;
    }

}; // class Day5 end


#endif //ALGOANDSTRUCT_DAY5_H
